public class Solution76 {

    private final int charToInt(char c)
    {
        if('a' <= c && c <= 'z')
        {
            return c - 'a';
        }
        return c - 'A' + 26;
    }

    private int[] getCountArr(String t)
    {
        int[] countArr = new int[52];
        for (int i = 0; i < t.length(); i++)
        {
            countArr[charToInt(t.charAt(i))]++;
        }
        return countArr;
    }

    private boolean isEquals(int[] tmpCharCount, int[] tCount)
    {
        for (int i = 0; i < 52; i++)
        {
            if(tmpCharCount[i] < tCount[i])
            {
                return false;
            }
        }
        return true;
    }

    public String minWindow(String s, String t)
    {
        int minWindowLeft = 0, minWindowRight = 0;
        boolean isSatisfied = false;
        int left = 0, right = 0;
        int[] tCount = getCountArr(t);
        int[] tmpCharCount = new int[52];
        tmpCharCount[charToInt(s.charAt(0))]++;
        while(right < s.length() && left <= right)
        {
            boolean wasEquals = false;
            while(isEquals(tmpCharCount, tCount) && left <= right){
                tmpCharCount[charToInt(s.charAt(left++))]--;
                wasEquals = true;
            }
            if(wasEquals){
                tmpCharCount[charToInt(s.charAt(--left))]++;
                if((right - left) < (minWindowRight - minWindowLeft) || !isSatisfied)
                {
                    isSatisfied = true;
                    minWindowLeft = left;
                    minWindowRight = right;
                }
            }
            right++;
            if(right < s.length())
            {
                tmpCharCount[charToInt(s.charAt(right))]++;
            }
        }
        return isSatisfied ? s.substring(minWindowLeft, minWindowRight + 1) : "";
    }


    public static void main(String[] args) {
        Solution76 s = new Solution76();
        s.minWindow("a", "a");
    }
}
